package com.mlamp.查找算法;

import com.mlamp.排序算法.基础排序;
import com.mlamp.排序算法.快速排序;

import java.util.Arrays;

public class 二分查找 {
    public static void main(String[] args) {
        int[] ints = 基础排序.generateArray(30);
        int[] ints1 = 快速排序.quickSort(ints, 0, ints.length - 1);
        System.out.println(Arrays.toString(ints1));
        for (int i = 0; i < ints1.length; i++) {
            int i1 = halfQuery(ints1, ints1[i]);
            System.out.println(String.format("target [%d] at loc %d", ints1[i], i1));
        }
        for (int i = 0; i < ints1.length; i++) {
            int i1 = recursiveHalfQuery(ints1, ints1[i], 0, ints1.length - 1);
            System.out.println(String.format("target [%d] at loc %d", ints1[i], i1));
        }


        int[] inputs = new int[]{
                1, 2, 3, 4, 5, 6
        };

        System.out.println("----------------");
        int targetLoc = biQuery3(inputs, 6);


        targetLoc = biqueryA(inputs, 3);


        System.out.println(targetLoc);

        targetLoc = biq(inputs, 5);
        System.out.println(targetLoc);

        targetLoc = biqu(inputs, 5);
        System.out.println(targetLoc);


    }

    public static int halfQuery(int[] array, int target) {
        int low = 0, high = array.length - 1, mid = -1;
        while (low <= high) {
            mid = low + (high - low) / 2;
            if (array[mid] == target) return mid;
            else if (array[mid] > target) {
                high = mid - 1;
            } else low = mid + 1;
        }
        return mid;
    }


    /**
     * 二分查找
     *
     * @param array
     * @param target
     * @return
     */

    public static int biq(int[] array, int target) {
        if (array == null || array.length == 0) throw new IllegalArgumentException("input error");
        int lo = 0, hi = array.length - 1;
        int mid = -1;
        while (lo <= hi) {
            mid = lo + ((hi - lo) >> 1);
            if (array[mid] == target) return mid;
            else if (array[mid] < target) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return mid;
    }


    public static int biqu(int[] array, int target) {
        assert array != null : "array is null";
        assert array.length > 0 : "array is empty";
        int left = 0, right = array.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (array[mid] == target) return mid;
            else if (array[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return -1;
    }


    public static int biQuery3(int[] array, int target) {
        if (array == null || array.length == 0) return -1;
        int low = 0, hi = array.length - 1;
        if (low > hi || target > array[hi] || target < array[low]) return -1;
        int mid = -1;
        while (low <= hi) {
            mid = low + ((hi - low) >> 1);
            if (target == array[mid]) return mid;
            else if (target > array[mid]) {
                low = mid + 1;
            } else if (target < array[mid]) {
                hi = mid - 1;
            }
        }
        return -1;
    }


    public static int biqueryA(int[] array, int target) {
        if (array == null || array.length < 1) throw new IllegalArgumentException("invalid array given");
        int lo = 0, hi = array.length - 1;
        int mid = -1;
        while (lo <= hi) {
            mid = lo + ((hi - lo + 1) >> 1);
            if (array[mid] == target) return mid;
            else if (array[mid] < target) lo = mid + 1;
            else if (array[mid] > target) hi = mid - 1;
        }
        return mid;
    }


    public static int biQuery2(int[] array, int target) {
        if (array == null || array.length == 0) return -1;
        int low = 0, hi = array.length - 1;
        int mid = -1;
        while (low <= hi) {
            mid = low + ((hi - low) >> 1);
            if (array[mid] > target) {
                hi = mid - 1;
            } else if (array[mid] == target) {
                return mid;
            } else {
                low = mid + 1;
            }
        }
        return mid;
    }


    public static int biquery(int[] array, int target) {
        int low = 0, hi = array.length - 1;
        int mid = -1;
        while (low <= hi) {
            mid = low + ((hi - low) >> 1);
            if (array[mid] == target) return mid;
            else if (array[mid] > target) hi = mid - 1;
            else low = mid + 1;
        }
        return mid;
    }

    public static int biQuery(int[] array, int targer) {
        int low = 0, hi = array.length - 1;
        int mid = -1;
        while (low <= hi) {
            mid = low + ((hi - low) >> 1);
            if (targer == array[mid]) return mid;
            else if (targer > array[mid]) low = mid + 1;
            else hi = mid - 1;
        }
        return mid;
    }

    public static int recursiveHalfQuery(int[] array, int target, int start, int end) {
        int mid = start + ((end - start) >> 1);
        if (target == array[mid]) return mid;
        if (target < array[mid]) return recursiveHalfQuery(array, target, start, mid - 1);
        if (target > array[mid]) return recursiveHalfQuery(array, target, mid + 1, end);
        return -1;
    }
}
